#include<iostream>
#include<vector>
#include<cstring>
#include<unordered_set>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool checkTree(TreeNode* root) {
        return root->val == root->left->val + root->right->val;
    }

    int xorOperation(int n, int start) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans ^= (start + i * 2);
        }
        return ans;
    }

    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] == nums[j])
                    ++ans;
            }
        }
        return ans;
    }

    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int n = arr.size(), cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (abs(arr[i] - arr[j]) <= a && abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c)  ++cnt;
                }
            }
        }
        return cnt;
    }

    string toLowerCase(string s) {
        for (char& ch : s) {
            if (ch >= 65 && ch <= 90) {
                ch += 32;
            }
        }
        return s;
    }

    int addDigits(int num) {
        while (num >= 10) {
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }

    int subtractProductAndSum(int n) {
        int sum = 0;
        int ji = 1;
        while (n > 0) {
            sum += n % 10;
            ji *= n % 10;
            n /= 10;
        }
        return ji - sum;
    }

    bool isPowerOfTwo(int n) {
        if (n <= 0)
            return false;
        if (n == 1)
            return true;
        if (n % 2 == 1)
            return false;
        else
            return isPowerOfTwo(n / 2);
    }

    bool isPowerOfThree(int n) {
        if (n <= 0)
            return false;
        if (n == 1)
            return true;
        if (n % 3 != 0)
            return false;

        else return isPowerOfThree(n / 3);
    }

    bool isUgly(int n) {
        if (n <= 0)
            return false;
        vector<int>factors = { 2,3,5 };
        for (int factor : factors) {
            while (n % factor == 0)
                n /= factor;
        }
        return n == 1;
    }

    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans(2 * n);
        for (int i = 0; i < n; i++) {
            ans[2 * i] = nums[i];
            ans[2 * i + 1] = nums[i + n];
        }
        return ans;
    }

    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> res(n, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }

    int maxScore(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 1; i < n; i++) {
            int score = 0;
            for (int j = 0; j < i; j++) {
                if (s[j] == '0')
                    score++;
            }
            for (int j = i; j < n; j++) {
                if (s[j] == '1')
                    score++;
            }
            ans = max(ans, score);
        }
        return ans;
    }

    int vowelStrings(vector<string>& words, int left, int right) {
        unordered_set<char>vowels = { 'a','e','i','o','u' };
        int ans = 0;
        for (int i = left; i <= right; i++) {
            const string& word = words[i];
            if (vowels.count(word[0]) && vowels.count(word.back())) {
                ans++;
            }
        }
        return ans;
    }

    int peakIndexInMountainArray(vector<int>& arr) {
        int flag = 0, max = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] >= max) {
                max = arr[i];
                flag = i;
            }
        }
        return flag;
    }
};

